package com.lx.algorithm.LinkedList;

/**
 * Description: 单链表练习
 * Copyright:   Copyright (c)2019
 * Company:     zefu
 *
 * @author: 张李鑫
 * @version: 1.0
 * Create at:   2021-09-20 18:58:39
 * <p>
 * Modification History:
 * Date         Author      Version     Description
 * ------------------------------------------------------------------
 * 2021-09-20     张李鑫                     1.0         1.0 Version
 */
public class NodeTest {
    public static class Node {
        private Node next;
        private Integer value;

        public Node(Integer value) {
            this.value = value;
        }
    }

    /**
     * 将单向链表按某值划分成左边小、中间相等、右边大的形式
     * <p>
     * 1）把链表放入数组里，在数组上做partition（笔试用）
     * <p>
     * 2）分成小、中、大三部分，再把各个部分之间串起来（面试用）
     */

    public static Node merge(Node node, Integer value) {
        //首先创建6个常数项
        Node sStart = null;
        Node sEnd = null;

        Node mStart = null;
        Node mEnd = null;

        Node bStart = null;
        Node bEnd = null;

        Node next =null;
        while (node != null) {
            next=node.next;
            node.next = null;
            if (node.value > value) {
                if (bStart == null) {
                    bStart = node;
                    bEnd = node;
                } else {
                    bEnd.next = node;
                    bEnd = node;
                }
            } else if (node.value.equals(value)) {
                if (mStart == null) {
                    mStart = node;
                    mEnd = node;
                } else {
                    mEnd.next = node;
                    mEnd = node;
                }
            } else if (node.value < value) {
                if (sStart == null) {
                    sStart = node;
                    sEnd = node;
                } else {
                    sEnd.next = node;
                    sEnd = node;
                }
            }
            node = next;
        }
        if (sEnd != null) {
            if (mEnd != null) {
                sEnd.next = mStart;
            } else {
                sEnd.next = bStart;
            }
        }
        if (mEnd != null) {
            mEnd.next = bStart;
        }

        return sStart != null ? sStart : ((null != mStart) ? mStart : bStart);
    }


    public static Node partition(Node node) {

        return new Node(1);
    }

    public static void main(String[] args) {
        Node head1 = new Node(7);
        head1.next = new Node(9);
        head1.next.next = new Node(1);
        head1.next.next.next = new Node(8);
        head1.next.next.next.next = new Node(5);
        head1.next.next.next.next.next = new Node(2);
        head1.next.next.next.next.next.next = new Node(5);
        head1.next.next.next.next.next.next.next = new Node(9);
        head1.next.next.next.next.next.next.next.next = new Node(9);
        head1.next.next.next.next.next.next.next.next.next = new Node(3);
        head1.next.next.next.next.next.next.next.next.next.next = new Node(3);
        head1.next.next.next.next.next.next.next.next.next.next.next = new Node(3);
        printLinkedList(head1);
        // head1 = listPartition1(head1, 4);
        head1 = merge(head1, 5);
        printLinkedList(head1);
    }

    public static void printLinkedList(Node node) {
        System.out.print("Linked List: ");
        while (node != null) {
            System.out.print(node.value + " ");
            node = node.next;
        }
        System.out.println();
    }



}